package leetcode.code0327;

public class Solution extends Solution327 {

	public class MaxSums {

		int[] nums;
		int len;
		long[] preSums;

		public MaxSums(int[] nums) {
			this.nums = nums;
			this.len = nums.length;
			this.preSums = new long[len + 1];
		}

		public long[] preSum() {
			preSums[0] = nums[0];
			for (int i = 1; i < len; i++) {
				preSums[i] = preSums[i - 1] + nums[i];
			}
			return preSums;
		}

		public long preSum(int x, int y) {
			return x == 0 ? preSums[y] : preSums[y] - preSums[x - 1];
		}

	}

	public class MaxMerge {

		private long array[];

		public MaxMerge(long[] array) {
			this.array = array;
		}

		public int process(int L, int R) {
			if (L == R) {
				return array[L] >= lower && array[L] <= upper ? 1 : 0;
			}
			int M = L + ((R - L) >> 1);
			return process(L, M) + process(M + 1, R) + merge(L, M, R);
		}

		public int merge(int L, int M, int R) {
			int ans = 0;
			int l = L, r = L;
			for (int i = M + 1; i <= R; i++) {
				long sum = array[i];
				long min = sum - upper, max = sum - lower;
//				[l,r)
				while (r <= M && array[r] <= max) {
					r++;
				}
				while (l <= M && array[l] < min) {
					l++;
				}
				ans += r - l;
			}
			long[] help = new long[R - L + 1];
			int p = 0;
			int p1 = L, p2 = M + 1;
			while (p1 <= M && p2 <= R) {
				help[p++] = array[p1] <= array[p2] ? array[p1++] : array[p2++];
			}
			while (p1 <= M) {
				help[p++] = array[p1++];
			}
			while (p2 <= R) {
				help[p++] = array[p2++];
			}
			for (p = 0; p < help.length; p++) {
				array[L + p] = help[p];
			}
			return ans;
		}
	}

	long[] sums;
	int lower, upper;

	@Override
	public int countRangeSum(int[] nums, int lower, int upper) {
		this.lower = lower;
		this.upper = upper;
		int len = nums.length;
		MaxSums maxSums = new MaxSums(nums);
		sums = maxSums.preSum();
		MaxMerge mm = new MaxMerge(sums);
		return mm.process(0, len - 1);
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
